For 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)

3
votes
2answers
290 views

Alphabet subset

Consider the following sequence of letters: a,b,c,d,e,f,g,h,i,j,k,l,m,n. How many ways are there to arrange the letters into sets of any length (empty set included) such that no sequence contains ...
3
votes
4answers
728 views

Trying to find $\sum\limits_{k=0}^n k \binom{n}{k}$ [duplicate]

Possible Duplicate: How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$? $$\begin{align} &\sum_{k=0}^n k \binom{n}{k} =\\ &\sum_{k=0}^n k ...
2
votes
2answers
585 views

Number of ways to fill 1,2,3,4 in an array so that the sum of each row & column is divisible by 4

There is a 4X4 array each entry of which can be filled with the numbers 1,2,3,4. In how many ways can we fill the array such that the sum of each row and each column is divisible by 4?
2
votes
1answer
1k views

Number of ways to put N indistinct objects into M indistinct boxes

Could anyone please tell me if there is a way to know the number of ways to put N indistinct objects into M indistinct boxes? I already know how to calculate the number of ways if any or both objects ...
0
votes
2answers
245 views

Partition of sets

Each domino piece is marked by two numbers. The pieces are symmetrical so the number pairs are not ordered. How many different pieces can be made using $ \{1,2,\dots,n\} $.
1
vote
1answer
52 views

The lower bound on the number of numbers needed to fill a matrix in a special way.

Let's take any natural number $n>0$. Let $k$ be the smallest natural number greater than $n/2.$ Now let $A$ be any $n$-element set, and let $M$ be a $k\times k$ matrix over $A$. Suppose that for ...
10
votes
1answer
402 views

Involutions and Abelian Groups

Suppose that $ G $ is a finite group where at least three-fourths of the elements are involutions, i.e., $$ |I(G)| \geq \frac{3}{4} |G|. $$ (Here, $ I(G) $ denotes the set of all involutions of $ G $, ...
0
votes
1answer
158 views

Is Lottery probability really the same for all combos?

http://justwebware.com/uklotto/uklotto.html Test run quickpick Test run 1,2,3,4,5,6 Test run (single digit,teens,twenties,twenties,thirties,forties) 1000 times or more each cycle for as many ...
4
votes
0answers
130 views

A general Combinatorics problem (Coefficients of the q factorial)

I was solving a combinatorics problem when I encountered difficulties. The problem was: $x_1 \in \{0,1\}$ $x_2 \in \{0,1,2\}$ . . $x_{n-1}\in\{0,1,2..,n-1\}$ We have to find the number of ways ...
3
votes
0answers
65 views

Maximum |E| on a given degree-diameter — Reference request

Given $d$, $k$ and $n$ of a graph G where $n$: the number of vertices in G, $d$: the maximum vertex-degree in G, $n$: the exact diameter of G, what is maximum possible $|E|$ ? That is, what is ...
5
votes
1answer
166 views

I've come up with two solutions to this problem, and I don't know which is correct.

If I have 5 distinct pair pairs of gloves, 10 distinct gloves in all, how many ways are there to distribute two gloves to each of 5 children if the two gloves someone receives can also be two left- or ...
2
votes
0answers
396 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
2
votes
0answers
117 views

Unavoidable structure of this kind of function:$Z\rightarrow N$.

Suppose that $f$:$Z\rightarrow N$ is a surjection and $|f^{-1}(n)|=2$ for every $n\in N$. I found that there is $n\in Z$ such that $f(n)$, $f(n+1)$, $f(n+4)$, and $f(n+5)$ differ from each other. ...
5
votes
1answer
336 views

Bijection between derangements and good permutations

A good permutation is a permutation of the numbers 1 to n, such that i is not followed by i+1 at any position in the permutation, for any i in {1,2,..,n-1}. Call the number of such permutations S(n). ...
7
votes
1answer
200 views

Who conjectured that there are only finitely many biplanes, and why?

This question on MathOverflow motivates me to ask what the reasoning is behind the conjecture that there are only finitely many biplanes. More generally, it has been conjectured that for fixed ...
1
vote
1answer
77 views

How to approach this problem of combinatorics

How many different numbers can be formed by the product of two or more of the numbers 3, 4, 4, 5, 5, 6, 7, 7, 7? The question doesn't even make sense to me because it says "two or more," so I could ...
1
vote
2answers
48 views

Number of ways to choose the same food at a restaurant

$2$ people are choosing from a menu of 9 food items and must choose $3$ items on the menu each. How many ways are there in which person $1$ and person $2$ choose precisely one of the same menu items?
5
votes
1answer
232 views

Are these numbers $h_{r,s}$ irrational?

I came across these numbers in my work some time ago. This type of expressions do not exist in closed form (not to confuse with Vandermonde convolution), I already know that. To simplify I denote ...
0
votes
1answer
165 views

Total number of ways to arrange the prime divisor of a number so it can be written using M digits

How many ways we can arrange all the prime divisor of a number so it can be written using M factors, where M <=T. T is the total number of prime divisor of the give number N. Example:N=27, its ...
1
vote
1answer
66 views

$ A = x + y + z$, number of solutions in $Z$ if $x, y, z$ are bounded in intervals

For the equation $x + y = A$, it's easy, when you notice that when iterating over all possible $x$, the number of solutions for $y$ is $0$ at the beginning, then increases by $1$, then stays constant, ...
2
votes
3answers
568 views

How many different sudoku puzzles are there?

The answer: 6, 670, 903, 752, 021, 072, 936, 960, according to this site: http://www.technologyreview.com/view/426554/mathematicians-solve-minimum-sudoku-problem/ I have tried to get this number ...
1
vote
1answer
469 views

Combinations in tournament

A tournament includes P total players. The game played in rounds with teams of size T. Possible number of teams is (P T). Questions How would you calculate the number of total possible combinations ...
-1
votes
1answer
71 views

Integral solutions to $a_1 \cdot a_2 \cdots a_k = N$

How many integral solutions are possible for the equation $a_1 \cdot a_2 \cdots a_k = N$ where each of $a_1,a_2,\ldots,a_k $ satisfy the property $ 0 ≤ a_i ≤ 9 $?
2
votes
0answers
78 views

Does anyone know any specific example of such point set

Does anyone know any specific or explicit example of a set of $256$ points so that no $10$ are the vertices of a convex $10$-gon? Thanks in advance.
4
votes
2answers
927 views

Counting the number of paths through a grid graph traversing all vertices exactly once

So I asked a question on stack overflow and they suggested I migrate over here. I'm writing a program to solve the following problem: Given a grid of x by y dimensions, calculate the number of ...
1
vote
0answers
106 views

lazy counting - failing to check equivalence classes are distinct

Declaring that a set has 10 elements requires two things: find some elements show they are all distinct showing you have all of them Sometimes these are easier said than done. E.g. count all ...
-1
votes
1answer
51 views

Eight friends vote among five shops

Eight friends consider and vote for the five shops they want to go to. However there is no absolute winner, and shops chosen by less than two friends of the group are not considered before they vote ...
0
votes
0answers
123 views

Probability - Combinations and permutations

Please could someone advise if the following looks correct. I am preparing for an exam and this is the only way I can get any feedback on my work. The last 3 digits of a number have been erased. ...
0
votes
2answers
216 views

Prove that $2^n-k\choose k-1 $ is even with all $k,n\in \mathbb N $, $1\le k\le 2^{n-1}$

Prove that $2^n-k\choose k-1 $ is even with all $k,n\in \mathbb N $, $2\le k\le 2^{n-1}$ I'm stuck with it when solve a polynomial problem Should we expand it? Or may we can use induction? Thanks
6
votes
3answers
526 views

Binomial Theorem past exam question, what do I do?

I have trouble understanding what I'm supposed to do in some of these math questions. Here's an exam question from an old exam: Let $A$ be a set with $n$ elements. The number of subsets of $A$ with ...
3
votes
1answer
225 views

Lagrange inversion formula in 2 variables?

I have the following implicit equation for the function $G(x,y)$ in 2 variables: $$G \;=\; (1 + x\,G^2)\,(1 + y\,G^2)$$ I want to use a form of a multivariable Lagrange inversion formula but I'm ...
1
vote
2answers
487 views

How many ways to write one million as a product of three integers?

In how many ways can the number 1;000;000 (one million) be written as the product of three positive integers $a, b, c,$ where $a \le b \le c$? (A) 139 (B) 196 (C) 219 (D) 784 (E) None of the ...
2
votes
2answers
311 views

multiple xor (sum of parities)

If we have: $b_1 \oplus b_2 = b_1 (1 - b_2) + b_2 (1 - b_1)$ what is (or are, if there are different versions) the compact general formula for a multiple "summation": $b_1 \oplus b_2 \oplus \dotsb ...
2
votes
2answers
283 views

The rooks problem

3 rooks are arranged on a 27 times 27 chess board so that no rook is attacking another. How many places can a 4th rook be placed so that it is attacking exactly one other rook on the board
15
votes
2answers
390 views

Why are braid numbers of the form $Q_h^2$ or $2 \times Q_h^2$?

Consider two piles of $h$ playing cards each, all distinct. Repeatedly take one of the cards on top of one of these two piles and move it on top of one of two new piles, until both of the new piles ...
2
votes
3answers
674 views

How many distinct football teams of 11 players can be formed with 33 men?

Can anyone help me with this problem, I can't figure out how to solve it... How many distinct football teams can be formed with 33 men? Thanks!
0
votes
2answers
50 views

cookie group problem

How many ways there are to group 27 same cookies into 3 same groups, where each group contains at least 1? If the groups are distinct, then I can use the technique to calculate how many ...
2
votes
2answers
96 views

Counting pairs $(n,n+1)$ where $n$ and $n+1$ are both quadratic residues, etc.?

This is an interesting problem I read that has me stumped. Let $(RR)$ denote the number of pairs $(n,n+1)$ in the set $\{1,2,\dots,p-1\}$ such that $n$ and $n+1$ are both residues modulo $p$. Let ...
1
vote
2answers
169 views

Probability question for college

Sorry to post this really simple question about probability here but my hands are forced here.My little brother came home with a question which I needed to help him solve. The only problem here is ...
7
votes
1answer
170 views

Is n! mod p doable in sub O(n) time?

I ask because I can use Lucas Theorem to find n choose k mod p but don't know of an equivalent for permutations (n permute k mod p).
0
votes
2answers
108 views

In the game of roulette there are 36 numbers that the ball may land on, other than the Zero.

In the game of roulette, there are a few known (and playable) number pairs of 18 numbers each. The black/red, the even/odd, and the high/low numbers are known. But how many combinations of 18 ...
1
vote
1answer
86 views

Number of pieces' arrangements on a chessboard.

I am interested how to calculate the number of arrangements of a given set of chess pieces on a given board that can be of a non-square rectangular shape too. ( I am not a native speaker so please ...
7
votes
8answers
1k views

Books/Resources on generating functions

I'm currently doing a research on generating functions, but I have only found few books on this topic. Can anyone provide references (if possible, trying to assess the level of math competence ...
1
vote
2answers
73 views

Throw 4 equal dice such that all of the faces show different numbers

Imagine one throws 4 equal dice at the same time. How many combinations with different faces (in which no face appears twice) are possible? For the first die one has 6 possible faces, for the second ...
2
votes
3answers
1k views

Counting the number of ordered triples

How would I count the the number of ordered triples of different numbers $(X_1, X_2, X_3)$, where $X_i$ could be any positive integer from $1$ to $N_i$, inclusive $(i = 1, 2, 3)$. If the input was ...
0
votes
0answers
51 views

Approach to generating matrix for this recurence relation

$$f(x,y)=f(x,y-1)+f(x/2,y-1)+f(x/3,y-1)+\ ...\ +f(x/9,y-1)$$ I'm new to matrix exponentiation concept and need help in generating the state-transition matrix for the relation This relation is related ...
1
vote
2answers
327 views

Counting the number of distinct greatest common divisors for an integer.

What is the expression for the number of distinct greatest common divisors possible for the number $N$? Let us say that $N$ is composed of 4 prime numbers $N = p_3 p_2 p_1 p_0$. Now if $p_i$ are all ...
3
votes
2answers
502 views

Proof involving Stirling numbers of the second kind

For all real numbers $x$, and all non-negative integers $n$, $$ x^n = \sum_{k=0}^{n} S(n,k)\frac{x!}{(x-k)!} $$ I have a 2 questions with the proof that my textbook presents. First they say that ...
4
votes
3answers
175 views

Number of solutions for $x[1] + x[2] + \ldots + x[n] =k$

Omg this is driving me crazy seriously, it's a subproblem for a bigger problem, and i'm stuck on it. Anyways i need the number of ways to pick $x[1]$ ammount of objects type $1$, $x[2]$ ammount of ...
0
votes
1answer
53 views

Dividing all permutations

Suppose you're trying to solve the Traveling Sales Person problem by going over all possible paths. To do so, you have a number of computers. Each gets $(n-1)!/p$ paths to scan, where $p$ is the ...