This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

11
votes
1answer
114 views

Combinatorial question about sets of rational numbers

The following question came up in my research. Since lots of clever people post here, I thought I'd ask it. Recall that the group ring of a group $G$ is the abelian group $\mathbb{Z}[G]$ consisting ...
3
votes
2answers
794 views

$3n+1$ people are to be divided into 3 committees?

$3n+1$ people are to be divided into 3 committees, in such a way that every committee must have at least one member, and no person can serve on all three committees. In how many ways can they be ...
0
votes
1answer
154 views

Permutation with Natural Ordering

I have searched the web for this answer and now must ask a community. Hello community. So say i can choose n items out of a numbered list no higher than ...
4
votes
2answers
491 views

Limit of alternating sum with binomial coefficient

I need to find a limit, or approximation for $\sum\limits_{k=1}^{n} (-1)^k {n \choose k} \log(a+bk)$ for, say, an $a,b\in (0,10)$. It is not so important what values $a$ and $b$ have. It would be ...
3
votes
1answer
285 views

Algorithm to Find All Vital Edges in a Minimum Weight Spanning Tree

I am trying to locate an algorithm that can find ALL vital edges (edges whose deletion strictly increases the cost of the minimum weight spanning tree in the resulting graph) in a minimum weight ...
1
vote
1answer
148 views

Coefficient of $x^n$ in $\prod^n(1-x^j)^{-1}$

(2) I'm trying to give a combinatorial description of the $$ n^{\mathrm{th}} $$ of $$ ...
2
votes
1answer
64 views

Shift and Divide Operators

(1) I was trying to down an equation in $$S,D$$ (these are the shift and differential operators, respectively) satisfied by $$\sum_{n=0}^{\infty}n!x^n$$ Mainly, I am trying to interpret these and ...
2
votes
3answers
647 views

Combinatorial Probability-Rolling 12 fair dice

My text says, regarding combinatorial probability, "The number of outcomes associated with any problem involving the rolling of n six-sided dice is $6^n$." I know that in combinatorial probability ...
22
votes
2answers
518 views

Is the Maclaurin series expansion of $\sin x$ related to the inclusion-exclusion principle?

When I see the alternating signs in the infinite series expansion of $\sin x$, I'm reminded of the inclusion-exclusion principle. Could there be any way to visualize it in such a way? Also, is there ...
1
vote
1answer
132 views

Best Lipschitz constant

I am trying to find the Lipschitz constant for the following function: $$ f(\pi)=\left|\sum_{i=1}^{m}c_{\pi(i)}-\sum_{i=m+1}^{2m}c_{\pi(i)}\right|, $$ where $c_i \in R$ and $\pi$ is a permutation of ...
3
votes
1answer
131 views

Van Der Waerden without topological dynamics?

Applying topological dynamics to prove Van Der Waerden's theorem on the existence of monochromatic arithematic progression has now become a somewhat classical example of the power of topological ...
1
vote
1answer
347 views

Combinatorics, arrangements (edited)

"How many ways can the letters in the word SLUMGULLION be arranged so that the three L’s precede all the other consonants?" My work is below: Can someone also solve this ONLY using the multiplication ...
2
votes
2answers
201 views

more on outer automorphisms of $S_6$

A sequel to my earlier question: I've been doing some more concrete arithmetic with one of these outer automorphisms and it's working out just the way "they" say it will (e.g. $(123)(45)(6)$ goes to ...
3
votes
1answer
1k views

Finding the number of monotonic paths not crossing the diagonal

For great diagrams relating to the Catalan number and the number of monotonic paths not crossing the diagonal, see this: http://en.wikipedia.org/wiki/Catalan_number#Second_proof So why is the number ...
0
votes
3answers
3k views

Combinations of two sets

I'd like to confirm, what is the name of this combination, and if its calculated right: Set (a,b) is spread over set of (1,2,3) ...
2
votes
1answer
89 views

A problem on family of 3-element sets

Today I came up with this problem: Find all natural numbers $n$ such that there exist a family of $3$-element subsets of the set $\{1,2,...,n\}$ like $\mathbf F$ such that: a) For all distinct $1\le ...
1
vote
1answer
76 views

Pool of $N$ ranked items, pick $P$ at random; chances of selecting 3 of top 5 ranks?

I have $N$ items with a number on them, ranked $1,2,3,4,5,\dots,N$, and I select $P$ items at random. What are the chances that 3 of the top 5 numbered items are in the $P$ chosen items?
1
vote
1answer
153 views

Permutation by interchange.

I made a conjecture today Start from $1, \ldots, n$, by interchanging the position of $i$ and $j$ where $i < j$ in each step, we are able to get any permutation of $\{1, \ldots, n\}$. Do you ...
1
vote
2answers
950 views

Find smallest number which is divisible to $N$ and its digits sums to $N$

Someone asked this question in SO: $1\le N\le 1000$ How to find the minimal positive number, that is divisible by N, and its digit sum should be equal to N. But I wonder if we don't have ...
3
votes
3answers
1k views

Keeping track of how to calculate probability/permutations/combinations?

I'm absolutely terrible at calculating these things and I would like to, especially with SATs coming up, improve my capabilities. What always gets me is that there are so many types of ways to ...
1
vote
1answer
326 views

Paths in a full graph

Given a complete graph with $4$ nodes, and one node is labeled $X$, find how many paths of length $N$ (might visit a node more than once) begin, end or both begin and end with $X$. This is not a ...
0
votes
3answers
112 views

Why does $10 \choose 7$ work in this case?

On a $10$ question true/false test, if the questions are answered at random, what is the probability of answering exactly $7$ questions correctly? I see how $10 \choose 7$ would be choosing $7$ ...
0
votes
1answer
162 views

A question on partial Bell polynomials

The partial Bell polynomials are given by : $$B_{n,k}(x_{1},x_{2},...,x_{n-k+1})=\sum \frac{n!}{j_{1}!j_{2}!...j_{n-k+1}!}\left(\frac{x_{1}}{1!} \right )^{j_{1}}\left(\frac{x_{2}}{2!} \right ...
9
votes
1answer
297 views

outer automorphisms of $S_6$

$$ \begin{array}{|l|c|c|} \hline \text{cycle structure} & \text{number of permutations} & \text{order} \\ \hline 6 & 120 & 6 \\ 5+1 & 144 & 5 \\ 4+2 & 90 & 4 \\ ...
2
votes
1answer
173 views

What are the relationships between combinatorics and randomness?

I was just reading the impressive paper by Tim Gowers The Two Cultures of Mathematics when I noticed the various connections between combinatorics and randomness. As a non-mathematician, it is not ...
4
votes
1answer
158 views

Proof by probabilistic argument

This is actually not a homework problem, but I'd like it to be treated as if it were one. I am not looking for a solution, I would just like to have some hints on how to start. I am trying to solve ...
1
vote
1answer
84 views

How many natural multisets exist with a given sum?

Given natural number $n$, how many multisets are there which sum of their elements equals $n$? There is a recursive function which can give the value in $O(n^2)$, but is there a formula for that? ...
0
votes
1answer
97 views

Given a positive integer, find the maximum distinct positive integers that can form its sum

For example, 6 has a max of 3 distinct integers excluding 0 that can form its sum (1,2,3). I can't think of any property that that I could exploit, even the recursions do not have good base cases.
1
vote
3answers
182 views

Submodularity Proof

For a fixed set $T$ and for sets $A_i ,\forall i \in \left \{ 1,2,\dots,n \right \}$ , I define $f(A_i)=\frac{|A_i|+|T|}{|A_i\cup T|}$, where $|A_i|$ is the cardinality of set $A_i$. Is $f(A_i)$ ...
4
votes
2answers
841 views

Recurrence for number of regions formed by diagonals of a convex polygon.

I've been having trouble with this particular problem, been thinking for it for a good hour or two, but I haven't gotten an explanation to the following question. Suppose $a_n$ be the number of ...
4
votes
1answer
102 views

Greatest Common Divisor of Several Integers

Let $N=\{a_1,a_2,...,a_n\}$ be a set of integers each $\ge$ $1$. Let $P(k)$ be the product of the ${n\choose k}$ LCMs of all the $k$-blocks of $N$ (subsets of $N$ with $k$ elements). Problem: Show ...
2
votes
0answers
53 views

Which type of counting problems are solved by hypergeometric function as generating function?

Which type of counting problems are solved by hypergeometric function as generating function? would you mind giving some examples such as relating counting with hypergeometric function as generating ...
1
vote
1answer
347 views

Solve non-homogeneous recurrence relation

I'm stuck on a recurrence relation that arises in a simulation I'm writing. Does anybody know how to proceed on this? I'm not even sure, because of the variable coefficient, how to get the associated ...
3
votes
2answers
191 views

Number of solutions to $a_1 + a_2 + \dots + a_k = n$ where $n > 0$ and $0 < a_1 \leq a_2 \leq \dots \leq a_k$ are integers.

I know how to find the number of solutions to the equation: $$a_1 + a_2 + \dots + a_k = n$$ where $n$ is a given positive integer and $a_1$, $a_2$, $\dots$, $a_n$ are positive integers. The number ...
2
votes
1answer
270 views

Binomial coefficient $\sum_{k \leq m} \binom{m-k}{k} (-1)^k$

This is example 3 from Concrete Mathematics (Section 5.2 p.177 in 1995 edition). Although the proof is given in the book (based on a recurrent expression), I were trying to find an alternative ...
1
vote
1answer
74 views

Encoding of a combination

If you have a set of $n$ integers ranging from $1$ to $n$ and you need to pick (create a tuple with length) $\sqrt{n}$ ($n$ is a valid square). One could encode that with an integer ranging from $1$ ...
2
votes
1answer
73 views

Inverse of $(1-t)^s$ in the power series ring

I am trying to find the inverse of $(1-t)^s$ in $k[[t]]$. I found out in literature that it should be $\sum\limits_{n \geq 0} \binom{s+n-1}{s-1}t^n$, but I don't see why. If I expand the element ...
16
votes
4answers
592 views

How to solve $\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2$?

I have tried something to solve the series $$\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2.$$ My approach is : $$(1+x)^n=\binom{n}{0} + \binom{n}{1}x + ...
2
votes
1answer
122 views

Geometrical combinatorics

This question was inspired by Rush Hour game: You have a 6x6 grid, 12 pieces of size 2, and 4 pieces of size 3. A piece can be placed on the grid either horizontally or vertically. The pieces can't ...
2
votes
2answers
123 views

Probability Combinatorial related; choosing couples

7 girs and 3 boys are divided to couples, order within a couple and between couples is not important, what is the probability that one of the couples contains 2 boys? i had this exercise in my ...
1
vote
2answers
8k views

How many 8-character alphanumeric passwords with 2 digits are there?

I am working on a homework problem where I need to find the total number of passwords that have exactly 8 characters. Constraints: each character is either an uppercase letter (A..Z) or a digit ...
0
votes
1answer
97 views

understanding the solution for “Expectation of the difference of sums”

I found the question Expectation of the difference of sums on this site, and I am trying to understand the solution, which uses the variance of the vector $a$. Please help me to understand the ...
0
votes
1answer
74 views

How to polynomial count when part of them do not repeat?

Assume 5 distinguished balls drawn randomly to 4 distinguished boxes, one ball one box mark the ball number on the box after drawn and put back the ball back to the pool and then draw again imagine ...
2
votes
1answer
113 views

How to find the best combinations

I have twelve items, each having a value, v. I'd like to group them into 6 pairs that are the best distribution of value across the set. I'd like them to be distributed in such a way that I have the ...
11
votes
6answers
770 views

How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?

I got stuck at the computation of the sum $$ \sum\limits_{k=0}^n (-1)^k{2n-k\choose k}. $$ I think there is no purely combinatorial proof here since the sum can achieve negative values. Could you ...
4
votes
1answer
125 views

Is $(p,\epsilon,p)$ a path of an automaton?

$A$ is an alphabet. An automaton over $A$ can be defined as a set $A_0 = (Q, E, I, T),$ where $Q$ is the set of states, $E \subseteq Q \times A \times Q$ is the set of edges or transition, $I, T ...
1
vote
2answers
136 views

How many roots lie in the interval $(0,1)$?

If $p$th , $q$th , $r$th term of a Geometric Progression be a $27 , 8$ and $12$ respectively, then how many root of the quadratic equation $ px^2 + 2qx -2r = 0 $ lie in the interval $(0,1)$ ? ...
-1
votes
2answers
130 views

how to prove an integer inequality

Given a positive integer $n$, is there a simple way to see that $$ (n+3)^{n+2}(2n+5)^{n+2}(n+1)^{n+2}(2n+1)^n \ge (n+2)^{2n+4}(2n+3)^{2n+2} $$ Any hint is welcome.
2
votes
1answer
1k views

Permutations and Combinations - How many different ways to do certain things before having to repeat?

Recently, while reading, I came across a problem in Problem Solving Strategies: Crossing the River with Dogs by Ken Johnson and Ted Herr that I was not entirely sure how to solve. Alas, I have come ...
0
votes
3answers
342 views

How to solve this with discrete math *Pokemon Trainers!*

There is a contest with 40 Pokemons. There are 18 Pokemons who like to fight in the sky, and 23 who like to fight on ground. Several of them like to fight in water. The number of those who like to fight ...